package com.lans.graph;

import com.lans.linear.Stack;

/**
 * @author: lans
 * @date: 2025/3/9
 * @name: 刘宇
 * 路径查找
 */
public class DepthFirstPaths {

    private boolean[] marked;

    //起始位置
    private  int s;

    private int[] edgeTo;

    public DepthFirstPaths(Graph G, int s) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s  = s;
        dfs(G,s);
    }

    private void dfs(Graph G, int v) {
        marked[v] = true;
        for(Integer w:G.adj(v)){
            if(!marked[w]){
                edgeTo[w]=v;
                dfs(G,w);
            }
        }
    }

    public boolean hasPathTo(int v) {
        return marked[v];
    }

    //路径
    public Stack<Integer> pathTo(int v){
        if(!hasPathTo(v)){
            return null;
        }
        Stack<Integer> path  = new Stack<>();
        for(int x=v;x!=s;x=edgeTo[x]){
            path.push(x);
        }
        path.push(s);
        return path;
    }
}